import collections

def to_canonical_edge(u, v):
    """将无向边标准化，确保 (u, v) 和 (v, u) 被视为同一条边"""
    return tuple(sorted((u, v)))

def find_all_simple_paths_dfs(start, end, current_adj_map, current_path, visited_nodes_in_path, all_paths_list):
    """
    在给定邻接表和访问集合下，通过 DFS 查找从 start 到 end 的所有简单路径。
    current_path: 当前递归路径中的节点列表
    visited_nodes_in_path: 记录当前路径中已访问的节点，用于避免环路和确保路径简单
    all_paths_list: 存储找到的所有路径
    """
    current_path.append(start)
    visited_nodes_in_path.add(start)

    if start == end:
        # 找到一条从 start 到 end 的简单路径
        all_paths_list.append(list(current_path))
    else:
        for neighbor in current_adj_map[start]:
            if neighbor not in visited_nodes_in_path:
                find_all_simple_paths_dfs(neighbor, end, current_adj_map, current_path, visited_nodes_in_path, all_paths_list)

    # 回溯：移除当前节点，允许其他路径使用它
    visited_nodes_in_path.remove(start)
    current_path.pop()


def find_nonisomorphic_cycles(graph_vertices, graph_edges):
    """
    找出图中所有的非同构（即独特的简单环实例）。
    graph_vertices: 图的顶点集合
    graph_edges: 图的边集合 (已规范化为 frozenset of canonical tuples)
    """
    # 构建可变的邻接列表
    current_adj = collections.defaultdict(set)
    for u, v in graph_edges:
        current_adj[u].add(v)
        current_adj[v].add(u)

    found_cycles_canonical = set() # 存储规范化后的环（以边的 frozenset 形式）

    # 遍历图中的每一条原始边 (u, v)
    for original_edge in graph_edges:
        u, v = original_edge

        # 1. 暂时从图中移除这条边
        current_adj[u].remove(v)
        current_adj[v].remove(u)

        # 2. 在剩余的图中，查找从 u 到 v 的所有简单路径
        list_of_paths = []
        # 调用 DFS 寻找路径，确保路径中的节点不重复（简单路径）
        find_all_simple_paths_dfs(u, v, current_adj, [], set(), list_of_paths)

        # 3. 对于找到的每一条路径，与被移除的边组合形成一个环
        for path in list_of_paths:
            # 路径 [u, ..., v] 加上原始边 (u,v) 构成一个环
            cycle_edges_for_this_cycle = set()
            for i in range(len(path) - 1):
                n1, n2 = path[i], path[i+1]
                cycle_edges_for_this_cycle.add(to_canonical_edge(n1, n2))

            # 添加被移除的原始边来完成环
            cycle_edges_for_this_cycle.add(original_edge)

            # 将环的边集合转换为 frozenset 并添加到结果集中，自动处理重复
            found_cycles_canonical.add(frozenset(cycle_edges_for_this_cycle))

        # 4. 恢复被移除的边，以便下一次迭代
        current_adj[u].add(v)
        current_adj[v].add(u)

    return list(found_cycles_canonical)

# --- 定义 Figure 17.1 中的图 ---
graph_vertices = frozenset(range(13)) # 0 到 12
raw_edges = [
    (0, 5), (5, 4), (7, 8),
    (4, 3), (0, 2), (9, 11),
    (0, 1), (11, 12), (5, 3),
    (9, 12), (9, 10), (6, 4),
    (0, 6)
]

# 将边标准化 (u,v) -> (min(u,v), max(u,v)) 并去重
graph_edges = frozenset([to_canonical_edge(u, v) for u, v in raw_edges])


# --- 查找并打印所有非同构的环 ---
cycles_found_by_edges = find_nonisomorphic_cycles(graph_vertices, graph_edges)

print(f"在 Figure 17.1 的图中，找到的独特简单环实例（非同构环）总数为: {len(cycles_found_by_edges)}")

# --- 将环的边集表示转换为路径表示以便展示 ---
cycle_list_for_display = []
for cycle_edge_set in cycles_found_by_edges:
    # 为了将边集合转换回可读的路径形式，需要重建一个临时邻接表并进行遍历
    temp_adj_for_cycle = collections.defaultdict(list)
    nodes_in_cycle = set()
    for u, v in cycle_edge_set:
        temp_adj_for_cycle[u].append(v)
        temp_adj_for_cycle[v].append(u)
        nodes_in_cycle.add(u)
        nodes_in_cycle.add(v)

    # 找到环的起始节点（任意一个即可，例如最小的节点）
    start_node = min(nodes_in_cycle) # 或者 next(iter(nodes_in_cycle))
    current_node = start_node
    path_nodes = [start_node]
    visited_cycle_nodes_for_path = {start_node}

    # 由于是简单环，每个节点的度数在其自身子图中应为2（除了首尾连接）
    # 沿着路径前进，直到所有节点都被访问，然后回到起点
    while len(path_nodes) < len(nodes_in_cycle):
        found_next_node = False
        for neighbor in temp_adj_for_cycle[current_node]:
            if neighbor not in visited_cycle_nodes_for_path:
                path_nodes.append(neighbor)
                visited_cycle_nodes_for_path.add(neighbor)
                current_node = neighbor
                found_next_node = True
                break
        if not found_next_node: # 异常情况，不应该发生在一个简单环中
            print(f"警告：无法完全遍历环以构建路径: {cycle_edge_set}")
            break

    path_nodes.append(start_node) # 闭合环

    cycle_length = len(path_nodes) - 1 # 环的长度等于边数

    cycle_list_for_display.append({
        'path': "-".join(map(str, path_nodes)),
        'length': cycle_length
    })

# 按照环的长度和路径进行排序，以便于阅读和验证
cycle_list_for_display.sort(key=lambda x: (x['length'], x['path']))

print("\n--- 找到的非同构环列表 ---")
for i, cycle_info in enumerate(cycle_list_for_display):
    print(f"环 {i+1}: 长度 {cycle_info['length']}, 路径: {cycle_info['path']}")